/*
 * @lc app=leetcode.cn id=659 lang=java
 *
 * [659] 分割数组为连续子序列
 */

// @lc code=start
class Solution {
    //贪心法，思路是维护两个hash表,这个方法时间，空间复杂度更优
    //贪心之处在于，每次拿到一个数x,如果m2中有x-1，那么k:x-1对应的v:-1，k:x对应的v:+1。
    // 如果m2中没有x-1，证明之前没有x-1结尾的序列，那么直接在m1中找x+1,x+2是否还有剩余，如果有都有剩余，可以组成一个长度为3的序列，在m1中k:x+1,x+2对应的v:-1。m2中k:x+2,v:+1。
    // 如果m1中没有剩余，直接返回false。好处在于不需要最后额外判断某个子序列是否小于3。
    public boolean isPossible(int[] nums) {
        //存每个数字出现的次数，k是数字，v是在nums中出现的次数
        Map<Integer,Integer> m1 = new HashMap<>();

        // k是数字，表示这个数字结尾的序列，v是个数，表示以k作为结尾序列的个数。注意不存序列的长度，默认只要大于3，才能存进来。
        Map<Integer,Integer> m2 = new HashMap<>();


        for(var x : nums){
            int count = m1.getOrDefault(x, 0) + 1;//getOrDefault意思是没有这个key，就设为0，有这个key，就是get的功能，拿到对应的value
            m1.put(x, count);
        }

        for(var x :nums){
            int count = m1.getOrDefault(x, 0);//这个数字的数量。为1则说明这个数字还有没用过的。
            //如果count==0只能说明这个数字被用完了，还得继续往后访问，不能停的。
            if(count>0){
                int prevEndCount = m2.getOrDefault(x - 1, 0);//先找有无以x-1结尾的子序列个数
                if (prevEndCount > 0) {//有
                    m1.put(x, count - 1);
                    m2.put(x - 1, prevEndCount - 1);
                    //x-1子序列对应个数-1
                    m2.put(x, m2.getOrDefault(x, 0) + 1);
                    //x子序列对应长度+1
                } else {//没有x-1为结尾的序列
                    int count1 = m1.getOrDefault(x + 1, 0);
                    int count2 = m1.getOrDefault(x + 2, 0);
                    if (count1 > 0 && count2 > 0) {//有x+1,x+2，可以组成一个长3的子序列
                        m1.put(x, count - 1);
                        m1.put(x + 1, count1 - 1);
                        m1.put(x + 2, count2 - 1);
                        m2.put(x + 2, m2.getOrDefault(x + 2, 0) + 1);
                    } else {//如果有一个为0，说明长度小于3，不满足要求。
                        return false;
                    }
                }
            }
        }
        return true;
    }
}


// class Solution1 {
//     //hash表+最小堆法
//     public boolean isPossible(int[] nums) {
//         Map<Integer, PriorityQueue<Integer>> map = new HashMap<Integer, PriorityQueue<Integer>>();
//         for (int x : nums) {
//             if (!map.containsKey(x)) {
//                 map.put(x, new PriorityQueue<Integer>());//如果不包含x，先插一个进来，注意这时候最小堆内无数值
//             }
//             if (map.containsKey(x - 1)) {
//                 int prevLength = map.get(x - 1).poll();
//                 if (map.get(x - 1).isEmpty()) {
//                     map.remove(x - 1);
//                 }
//                 map.get(x).offer(prevLength + 1);
//             } else {
//                 map.get(x).offer(1);//没有直接插入一即可
//             }
//         }
//         //扫描完整个数组之后，扫描map中的每个key值，其对应的小根堆中如果堆顶元素小于3，证明其序列长小于3，不符合要求
//         /**
//          * 增强型for循环的遍历方式。
//          * 由于Map中存放的元素均为键值对，故每一个键值对必然存在一个映射关系。
//             Map中采用Entry内部类来表示一个映射项，映射项包含Key和Value
//             Map.Entry里面包含getKey()和getValue()方法
//          */
//         Set<Map.Entry<Integer, PriorityQueue<Integer>>> entrySet = map.entrySet();
//         for (Map.Entry<Integer, PriorityQueue<Integer>> entry : entrySet) {
//             // Map.Entry里面包含getKey()和getValue()方法。这里由增强型循环getkey了。
//             PriorityQueue<Integer> queue = entry.getValue();
//             if (queue.peek() < 3) {
//                 return false;
//             }
//         }

//         /**
//          * 另一种遍历方式，用iterator
//          */
//         // Iterator<Map.Entry<Integer, PriorityQueue<Integer>>> it=map.entrySet().iterator();
//         // while(it.hasNext()){
//         //     Map.Entry<Integer, PriorityQueue<Integer>> entry = it.next();
//         //     PriorityQueue<Integer> queue = entry.getValue();
//         //     if (queue.peek() < 3) {
//         //         return false;
//         //     }
//         // }

//         // return true;
//     }
// }

// @lc code=end

